/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  // 通过层序遍历完成序列化
  let res = [] // 序列化数组
  let queue = [] // 生成一个队列
  if (root == null) return '#' // 如果是null直接返回#
  queue.push(root) // 否则吧根节点放入这个队列中
  while (queue.length) { // 当队列不为空
    let node = queue.shift() // 弹出头部

    if (node === null) {// 如果这个是空 就不进行下一步了
      res.push('#')
      continue
    }
    res.push(node.val)
    queue.push(node.left)
    queue.push(node.right)
  }
  return res.join(',') // 最后返回拼接的字符串
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  let nodes = data.split(',') // 分隔成数组
  if (nodes.length === 0) return null // 如果没有 就返回这个null
  // 第一个元素就是根节点的值
  let rootVal = nodes[0]
  let root = new TreeNode(rootVal) // 生成根节点
  let queue = [] // 初始化队列
  queue.push(root) // 放入根节点
  for (let i = 1; i < nodes.length;) {
    // 遍历这个nodes数组
    let parent = queue.shift() // 弹出父节点
    let left = nodes[i++] // 左节点就是下一个
    if (left !== '#') {
      // 如果下一个不是空 就让这个等于父节点的左子树
      parent.left = new TreeNode(left)
      queue.push(parent.left) // 把左子树压入到这个队列中
    } else {
      parent.left = null  // 否则这个左子树就是null 不需要进入队列
    }
    let right = nodes[i++] // 这个是右子树
    if (right === '#') {
      // 道理和左子树一样
      parent.right = null
    } else {
      parent.right = new TreeNode(right)
      queue.push(parent.right)
    }
  }
  return root
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */